﻿package util;

import java.util.Arrays;

/**
 * 
 * 排序算法的代码实现 参考：http://blog.csdn.net/fenglibing/archive/2007/08/23/1756473.aspx
 * 算法理论 参考：http://www.zsqz.com/jsbase/Suanfa/index.html?defination.htm
 * 
 */
public class SortUtil {
	public static void main(String[] args) {
		long[] src = new long[]{3,2,6,8,9,11,5};
		//doBubbleSort(src,true);
		//doChooseSort(src,true);
		
		//doSort(src, "", true);
		//doSort(src, "bubble", true);
		//doSort(src, "choose", true);
		doSort(src, "insert", true);
		
		for(int i = 0;i<src.length;i++){
			System.out.print(src[i] + " ");
		}
	}
	
	/**
	 * 
	 * @param src 待排序数组
	 * @param flag 排序方式
	 * @param isFromSmall 是否从小到大排序
	 */
	public static long[] doSort(long[] src,String flag,boolean isFromSmall){
		if(flag == null || "".equals(flag)){
			Arrays.sort(src);//升序排列
			if(!isFromSmall){//降序排列
				
			}
		}else if("bubble".equals(flag)){
			doBubbleSort(src, isFromSmall);
		}else if("choose".equals(flag)){
			doChooseSort(src, isFromSmall);
		}else if("insert".equals(flag)){
			doInsertSort(src, isFromSmall);
		}
		return src;
	}
	
	/**
	 * 根据排序方式判断是否交换数据
	 * @param src1
	 * @param src2
	 * @param isFromSmall 是否从小到大排序
	 * @return
	 */
	private static boolean isSwap(long src1,long src2,boolean isFromSmall){
		return isFromSmall == true ? (src1>src2) : (src1<src2);
	}
	
	/**
	 * 交换两个数
	 * @param src 待排序数组
	 * @param i
	 * @param j
	 * @param isFromSmall 是否从小到大排序
	 */
	private static void swap(long[] src,int i,int j){
		long temp = src[j];
		src[j] = src[i];
		src[i] = temp;
	}
	
	/**
	 * 冒泡排序(最简单的排序方法)
	 * 基本思想：将待排序的元素看作是竖着排列的"气泡"，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个"气泡"序列处理若干遍。
	  			所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，
	  			即"轻"的元素在下面，就交换它们的位置。显然，处理一遍之后，"最轻"的元素就浮到了最高位置；处理二遍之后，"次轻"的元素
	  			就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是"最轻"元素，所以不必检查。一般地，第i遍处理时，不必检查
	  			第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
	 * @param src 待排序数组
	 * @param isFromSmall 是否从小到大排序
	 * @return
	 */
	private static long[] doBubbleSort(long[] src,boolean isFromSmall) {
		int len = src.length;
		int i,j;
		for (i = 0; i < len; i++) {
			for (j = i + 1; j < len; j++) {
				if(isSwap(src[i], src[j], isFromSmall)){
					swap(src, i, j);
				}
			}

		}
		return src;
	}
	
	/**
	 * 选择排序
	 * 基本思想：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，
	 			第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
	 			  
	 * 选择排序与冒泡排序的不同：选择排序是先定位出下标再交换数据，而冒泡排序总是要不断的交换数据
	 * 
	 * @param src 待排序数组
	 * @param isFromSmall 是否从小到大排序
	 * @return
	 */
	private static long[] doChooseSort(long[] src,boolean isFromSmall) {
		int len = src.length;
		int i, j;
		for (i = 0; i < len; i++) {
			long temp = src[i];
			int location = i;// 最小数或最大数的下标
			for (j = i + 1; j < len; j++) {
				if(isSwap(temp, src[j], isFromSmall)){
					temp = src[j];
					location = j;// 重新定位最小数或最大数的下标
				}
			}
			swap(src, i, location);
		}
		return src;
	}
	
	/**
	 * 插入排序
	 * 基本思想：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。
	 			要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；
	 			否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
　　				简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种。

	 * @param src 待排序数组
	 * @param isFromSmall 是否从小到大排序
	 * @return
	 */
	private static long[] doInsertSort(long[] src,boolean isFromSmall) {
		int len = src.length;
		int i,j;
		for (i = 1; i < len; i++) {
			long temp = src[i];
			for (j = i; j > 0; j--) {
				if(isSwap(src[j - 1], temp, isFromSmall)){
					src[j] = src[j - 1];
				} else
					// 如果当前的数，不小于前面的数，那就说明不小于前面所有的数，因为前面已经是排好了序的，所以直接跳出当前一轮的比较
					break;
			}
			src[j] = temp;
		}
		return src;
	}

}
